\documentclass[12pt,oneside,a4paper]{article}   
\usepackage[czech, english]{babel}
\usepackage{amsmath}
\usepackage{epsf,epic,eepic,eepicemu,url,graphicx}
\usepackage[utf8]{inputenc}
\newenvironment{listing}
{\begin{list}{}{\setlength{\leftmargin}{1em}}\item\scriptsize\bfseries}
{\end{list}}

\begin{document}
\begin{center}
\bf Semestralní projekt MI-PAR 2010/2011:\\[5mm]
    Paralelní řešení úlohy MHR - Minimální hranový řez\\[5mm]
       Jiří Chadima (chadijir@fit.cvut.cz)\\
       Karel Svoboda (svoboka6@fit.cvut.cz)\\[2mm]
magisterské studium, FIT ČVUT, Kolejní 550/2, 160 00 Praha 6\\[2mm]
9.\,12.\,2010
\end{center}

\section{Zadání a popis úlohy}

Cílem úlohy je naprogramování sekvenční a~paralelní varianty algoritmu řešícího úlohu o~minimálním hranovém řezu. Tato úloha je jedním z~typických grafových problémů s~poměrně velkou výpočetní náročností a~druhou částí úlohy je tak i~změření reálné časové náročnosti obou algoritmů.

Minimální hranový řez je takové rozdělení množiny uzlů grafu do dvou disjunktních neprázdných podmnožin \(X\)~a~\(Y\) tak, že součet ohodnocení všech hran \({u,v}\) takových, že \(u\)~je z~\(X\)~a~\(v\)~je~z~\(Y\), je minimální.

Vstupem úlohy je vždy jednoduchý souvislý neorientovaný \(k\)-regulární graf o~\(n\)~uzlech a~\(m\)~hranách, za předpokladu, že \(n\geq 5\), \(n \geq k \geq 3\) a~\(n\)~a~\(k\) současně nejsou obě lichá. K~dispozici je program pro generování takových grafů, jeho výstupem je však graf s~neohodnocenými hranami. Podmínkou pro řešení úlohy je ale ohodnocení hran celočíselnými vahami z~intervalu \(<1, 255>\).

Toto ohodnocení zajišťuje námi vytvořený program, jehož vstupem je výstup grafového generátoru. Jeho výstupem je ohodnocený graf ve formátu (popsán níže), který je vstupem sekvenční i~paralelní implementace algoritmu. Tento krátký program lze dohledat na \cite{official}

Výstupem obou typů algoritmů je výpis disjuktních podmnožin uzlů \(X\)~a~\(Y\), všech hran tyto množiny spojující a~součet jejich ohodnocení. Dále programy vypisují údaj o~době běhu, která je zásadní pro závěrečné zhodnocení zejména paralelní implementace.

\section{Společné součásti}
\subsection{Vstup}
Vstupem sekvenčního i~paralelního programu je ohodnocený regulární graf zadaný počtem uzlů a~maticí incidence. Tato reprezentace grafu je uložena v~souboru, jehož jméno je prvním parametrem obou algoritmů. V~matici incidence jsou ohodnocení jednotlivých hran vždy odděleny mezerou. Ukázkový vstupní soubor pro 6~uzlů může vypadat například takto:
\begin{listing}
\begin{verbatim}
6
0 98 97 15 0 0 
98 0 73 0 18 0 
97 73 0 0 0 21 
15 0 0 0 249 38 
0 18 0 249 0 232 
0 0 21 38 232 0 
\end{verbatim}
\end{listing}

V~programu se graf načítá pouze z~horní trojúhelníkové matice, abychom ušetřili cenný čas. Načtené hodnoty jsou poté uloženy ve dvojrozměrném poli, které obaluje třída \texttt{Graph}, která zároveň obsahuje pole pro ukládání předem vypočítaných charakteristik.

\subsection{Výstup}
Výstupem programu je vždy výpis obsahující předpočítané charakteristiky grafu, které obsahují i~horní mez celého výpočtu, kterou je minimum ze součtu hran incidujících vždy s~jedním uzlem (jinými slovy jde o~řádek s~minimálním součtem). Dále je vypsána instance problému, tedy graf, a~také nejlepší nalezené řešení v~předepsaném formátu. Důležitou hodnotou je i~čas běhu výpočtu, který může pro malá \(n\) dosahovat i~velmi malých hodnot. Výstup obou programů pro výše uvedenou instanci vypadá zhruba takto:

\begin{listing}
\begin{verbatim}
Graph input
======================================= 
Nr. of nodes: 6
Regularity: 3
Min edge weight: 15
Max cut weight: 189
Max cut weight node: 1
    0:   0  98  97  15   0   0 
    1:  98   0  73   0  18   0 
    2:  97  73   0   0   0  21 
    3:  15   0   0   0 249  38 
    4:   0  18   0 249   0 232 
    5:   0   0  21  38 232   0 
Approximate running time: 0.000504971
Solution
======================================= 
X set: 0, 1, 2
Y set: 3, 4, 5
Connecting edges: [0,3][1,4][2,5]
Total cost: 54
\end{verbatim}
\end{listing}

\subsection{Reprezentace stavu}
Jednou z~klíčových součástí celého programu je reprezentace konkrétního stavu problému, v~tomto případě rozdělení jednotlivých uzlů do množin \(X\)~a~\(Y\). Z~důvodu paměťové úspory jsme jako datovou strukturu zvolili dynamicky alokované pole typu boolean, kde logická jedna znamená příslušnost do množiny \(X\)~a~logická nula příslušnost do množiny \(Y\). Kromě tohoto rozdělení obsahuje třída \texttt{State}, která obaluje tuto datovou strukturu, ještě privátní pole obsahující celkovou cenu takového řezu, ukazatel na objektovou reprezentaci řešeného grafu a~také číselný index uzlu, ze kterého bude možné stav nadále expandovat.

\section{Sekvenční algoritmus}
Popis zadání vychází z~informací na \cite{eduxTASK}. Sekvenční algoritmus je typu BB-DFS (branch and bound depth first search) s~hloubkou stavového stromu omezenou na \(n-1\). Toto omezení vyplývá z~toho, že množina \(Y\) bude obsahovat maximálně \(n-1\) uzlů. Při počáteční inicializaci se vygenerují stavy přiřazující vždy jeden uzel do množiny \(Y\). Vzniká tak \(n-1\) počátečních stavů, přičemž každý stav s~uzlem v~množině \(Y\) na pozici \(i\), má jako další uzel přidávaný do množiny \(Y\), nastavený uzel na pozici \( i+1\). Pakliže je \(i+1\) rovno \(n\), není takový stav již dále expandován.

Protože cena hranového řezu se může vylepšit pokaždé, když dochází k~přesunu nového uzlu do množiny \(Y\), není možné některé stavy zahazovat jako neperspektivní, je potřeba projít a~ověřit všechny dostupné stavy. Tyto stavy se vytváří vždy, když je ze zásobníku vytažen nový stav, a~to pomocí tohoto jednoduchého algoritmu:
\begin{listing}
\begin{verbatim}
for (i = current.getNextNode(); i < totalNodeCount; i++) {
    if (i+1 == totalNodeCount) continue;
    State st = State(current);
    st[i] = true;
    st.setNextNode(i + 1);
    st.countCost();
    myStack.push(st);
}
\end{verbatim}
\end{listing}
V~proměnné \texttt{current} je vždy uložen stav aktuálně vytažený ze zásobníku. Tento stav je považován za projitý a~dále se výpočtu neúčastní. proměnná \texttt{totalNodeCount} obsahuje číslo \(n\), tedy celkový počet uzlů. Cyklus proběhne vždy \((n-(k+1))\)-krát a~v~ideálním případě vznikne \((n-(k+1))\) nových stavů. V~každém nově vzniklém stavu je do množiny \(Y\) přesunut uzel na pozici \(i\)~a~jako další uzel, který bude přesunut do množiny \(Y\) je nastaven uzel na pozici \(i+1\). Metoda \texttt{countCost} zajistí předpočítání ceny celého řezu.

Jako konkrétní implementaci zásobníku jsme pro sekvenční algoritmus použili tu, která je dostupná ve standardní knihovně.

Tělo důležité metody \texttt{countCost} pak zapsané v pseudokódu vypadá jako na níže uvedeném výpisu. Převedeno do normální řeči jde o~algoritmus, který prochází všechny uzly, a~pokud je uzel v~množině \(Y\), hledají se hrany vedoucí mezi ním a~uzly v~množině \(X\). Ohodnocení těchto hran se poté přičítá k~výsledné ceně.
\begin{listing}
\begin{verbatim}
cena = 0;
for (i, všechny uzly) {
    if (uzel i v množině Y) {
        for (j, všechny uzly) {
            if (hrana existuje && uzel j v množině X) {
                cena += hodnota hrany i-j;
            }
        }
    }
}
\end{verbatim}
\end{listing}

Při každém získání stavu ze zásobníku je cena tohoto stavu porovnána s~doposud nejlepším nalezeným řešením. To je zpočátku nastaveno podle naivně předpočítané hodnoty, kdy je do množiny \(Y\) přesunut uzel s~nejmenším součtem ohodnocení hran s~ním incidujících.

\section{Paralelní algoritmus a jeho implementace v MPI}

Paralelní algoritmus je typu \textbf{PBB-DFS-V} (paralelní BB-DFS s~vždy úplným prohledáváním stavového prostoru, \cite{eduxDFS}) a~oproti sekvenční variantě se ve výpočetní části prakticky neliší. Liší se však tím, že je nutné řídit práci jednotlivých procesů podílejících se na paralelním výpočtu. Pro komunikaci mezi procesy je použita knihovna MPI.

Díky tomu, že použitá implementace MPI zvládá předat vstupní parametry všem spouštěným procesům, není potřeba řešit úvodní distribuci instance problému. Ze vstupního souboru je graf načten stejně jako při sekvenčním zpracování. Poté však již dochází k~úpravám algoritmu. Hlavní srdce celého programu leží v~metodě \texttt{Solver::solve}.

V~první fázi výpočtu proces označený MPI jako 0 (dále jako \textbf{root}) vygeneruje počáteční sadu stavů stejně jako v~případě sekvenčního algoritmu. Tyto stavy si uloží na lokální zásobník. Ve druhé fázi inicializace dochází k~distribuci těchto stavů ostatním procesům, kdy každý proces obdrží \(k / p\) stavů, kde \(k\) je počet stavů na zásobníku a~\(p\) je celkový počet procesů účastnících se výpočtu.

Při této činnosti je poprvé použit mechanismus dělení zásobníku. Oproti sekvenčnímu zpracování je v~paralelním programu zásobník implementován jako obousměrná fronta. Pro lokální činnost jsou stavy odebírány z~vršku (konce) fronty, pro dělení zásobníku jsou vybírány stavy zespod (začátku) fronty. Mechanismus dělení se tak dá popsat jako metoda \textbf{D-ADZ} (půlení u dna, \cite{eduxDFS}). Samotná operace je ošetřena ještě tak, aby docházelo k~co nejlogičtějšímu dělení. Některé stavy totiž mohou být vypočteny velice rychle a~není příliš efektivní je odesílat jinému procesu. V~našem konkrétním případě se jedná o~stavy, kde se při další expanzi dostane do množiny \(Y\)~uzel z~druhé poloviny množiny uzlů (na pozici \(k > n/2\)).

Komunikace mezi procesy je zajištěna metodami \texttt{MPI\_Send} a \texttt{MPI\_Recv}, u~procesu, který data přijímá je ještě použita metoda \texttt{MPI\_Get\_count}, která dokáže zjistit objem dat, který nám dorazil. Tohoto údaje je poté využito při deserializaci příchozího zásobníku. Jako datový typ obsahu zpráv je použit \texttt{MPI\_UNSIGNED\_CHAR}. Kromě metod pro serializaci zásobníku je použita i~metoda pro serializaci stavů. Metoda pro serializaci zásobníku v~podstatě jen spojuje serializované reprezentace stavů.

V~tuto chvíli má tedy každý proces na svém lokálním zásobníku nějakou sadu stavů a~může začít samotný výpočet minimálního hranového řezu. V~pseudokódu vypadá hlavní smyčka programu zhruba takto:
\begin{listing}
\begin{verbatim}
while (keepWorking) {
    if (v zásobníku jsou stavy) {
        získej aktuální stav z vrchu zásobníku
        spočítej hodnotu řezu v aktuálním stavu
        expanduj aktuální stav
    }
    if (zkontroluj zprávy) {
        if (prazdný zásobník && !čekám odpověď na žádost o práci) {
            if (pošli peška) {
                p+1 procesu pošli peška správné barvy
                barva procesu = bílá;
            }
            if (skonči) { // pouze root proces
                všem procesům kromě rootu pošli terminate
                keepWorking = false;
            }
            pomocí ACZ-AHD vyber proces, a ten požádej o práci
            čekám odpověď na žádost o práci = true;
        }

        MPI_Iprobe(MPI_ANY_SOURCE, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);
        if (flag) { // přišla zpráva
            přečti zprávu pomocí MPI_Recv
        } else { 
            iterace bez zpráv ++; continue;
        }
        
        switch (status.MPI_TAG) {
            case MSG_WORK_REQUEST: // někdo chce práci
                jestliže prázdný lokální zásobník, nebo nejde zásobník dělit                
                    odpověz, že nemůžeš dát práci
                jinak
                    rozděl zásobník
                    serializuj zásobník a pošli ho
                    pokud byl zásobník poslán procesu "doprava",
                    nastav barvu procesu na černou
            case MSG_NO_WORK_RESPONSE:
                čekám odpověď na žádost o práci = false;
                počet negativních odpovědí na žádost o práci ++
                if (jsem root a
                  počet negativních odpovědí je větší než počet procesů - 1) {
                    pošli bílého peška = true;
                }
            case MSG_WORK_RESPONSE:
                čekám odpověď na žádost o práci = false,
                počet negativních odpovědí na žádost o práci = 0
                přijmi a deserializuj zásobník
            case MSG_BLACK_TOKEN:
                jestliže jsem root
                    pošli bílého peška = true;                
                jinak
                    pošli černého peška = true;
            case MSG_WHITE_TOKEN:
                jestliže jsem root
                    skonči = true;
                jinak
                    pošli peška stejné barvy jako je proces
            case MSG_TERMINATE:
                keepWorking = false
            }
        }
    }
\end{verbatim}
\end{listing}

Hlavní smyčka výpočtu je řízena flagem \texttt{keepWorking} a~skládá se ze dvou částí. V~první části probíhá v~případě, že jsou k~dispozici nějaké stavy, výpočet a~expanze. Rovněž se načítá proměnná \texttt{counter}, která slouží k~detekci toho, kdy kontrolovat případné příchozí zprávy. Tato hodnota je nastavena na 100, tzn. že každých sto iterací hlavní smyčky probíhá komunikace s~ostatními procesy.

Každou stou iteraci tak dochází ke dvěma činnostem. Tou první je kontrola stavu procesu. Pokud je proces ve stavu nečinnosti, tedy nemá na zásobníku žádné stavy a~nečeká na práci, dochází k~řešení možných variant této situace.
Jako první se řeší, zda má algoritmus poslat nějakého peška, dále se testuje stavová proměnná řídící závěrečné ukončení výpočtu. Na závěr je po vyhledání vhodného dárce variantou \textbf{ACZ-AHD} (asynchroní cyklické žádosti, \cite{eduxDFS}) tento o~práci požádán a~je nastavena stavová proměnná.

Nehledě na to, zda je zásobník prázdný se pak vykonává část programu obsluhující příchozí komunikaci. Pomocí funkce \texttt{MPI\_IProbe} se otestuje, zda ve frontě nečeká nějaká zpráva a~pokud ano, přijme se. Příchozí zpráva je poté podle svého tagu zpracována v~konstrukci switch.

K~dispozici je trojice zpráv řídících výměnu práce, dvojice zpráv obsluhujících Algoritmus pro distribuované ukončení výpočtu (\textbf{ADUV}, \cite{eduxDFS}), tedy peška, a~zpráva nesoucí informaci o~ukončení výpočtu. ADUV je naprogramován způsobem uvedeným na \cite{eduxDFS}.

Výměna práce probíhá poměrně intuitivně. Při příjmu žádosti o~práci se proces pokusí rozdělit svůj zásobník a~část z~něj předat jinému procesu. To může vyústit ve dvě situace: odeslání několika stavů a~zprávy \texttt{WORK\_RESPONSE}, nebo zprávy \texttt{NO\_WORK\_RESPONSE}. Ať je přijmutá odpověď jakákoliv, proces si nastaví pomocnou proměnnou tak, že při příští iteraci s~prázdným zásobníkem zase požádá o~práci. Pokud proces root dostane na žádost o~práci od všech ostatních procesů negativní odpověď, vypustí mezi procesy bílého peška a~pokusí se ukončit výpočet.

Pakliže pokus o~ukončení výpočtu dopadne úspěchem, tedy procesu root se vrátí bílý pešek, root si uloží informaci o~tom, že při následující iteraci s~prázdným zásobníkem má ukončit lokální výpočet a~všem ostatním procesům poslat příkaz k~ukončení výpočtu. Po odeslání této zprávy končí hlavní výpočetní smyčka.

V~poslední fázi výpočtu je nutné shromáždit veškerá nejlepší lokální řešení a~z~nich vybrat to celkově nejlepší. MPI nabízí metody pro vykonání paralelní redukce, protože ale potřebujeme zobrazit ve výsledku celý stav včetně rozdělení uzlů do množin, nemůžeme je použít. Z~toho důvodu všechny procesy kromě procesu root odešlou své nejlepší řešení právě root procesu. Ten je postupně shromáždí a~sekvenčně z~nich vybere řešení s~nejmenším ohodnocením. Tento stav je poté prezentován uživateli jako nejlepší možné řešení dané instance problému minimálního hranového řezu.

\subsection{Spouštění a ladění paralelního algoritmu}
Program je vždy nutné zkompilovat pomocí přiloženého \texttt{Makefile}. Před kompilací je možné nastavit úroveň textového výstupu v~průběhu výpočtu v~hlavičkovém souboru \texttt{settings.h}. K~dispozici jsou tyto konstanty:
\begin{itemize}
\item \texttt{SHOW\_STATES} - Ukazuje veškeré procházené stavy.
\item \texttt{SHORT\_OUTPUT} - Nastavuje krátký výpis procházených stavů (pouze 1~a~0).
\item \texttt{MPI\_DEBUG} - Vypisuje všechny zprávy MPI týkajících se práce.
\item \texttt{MPI\_ADUV\_DEBUG} - Vypisuje všechny zprávy MPI týkající se ukončení výpočtu.
\item \texttt{SHOW\_TOTAL\_STATS} - Na závěr vypíše lokální statistiky výpočtu, mezi něž patří: počet projitých stavů, počet odeslaných a~přijmutých žádostí o~práci, počet přijatých kladných a~záporných odpovědí na žádost o~práci, počet odeslaných bílých a~černých pešků.
\end{itemize}

Program lze úspěšně spustit na jakémkoliv linuxovém stroji s~nainstalovaným \textbf{openmpi} např. pomocí následujícího příkazu, kde parametr \textit{n}~určuje počet procesorů, \textit{par-mhr} je jméno binárky a~\textit{test/test-6nodes} je soubor s~instancí grafu.
\begin{listing}
\begin{verbatim}
mpiexec -n 2 par-mhr tests/test-6nodes 
\end{verbatim}
\end{listing}

Na výpočetním clusteru \textbf{star.fit.cvut.cz}, kde probíhalo testování, je použit plánovač úloh Sun Grid Engine \cite{eduxSTAR}, na němž se úlohy spouští pomocí následujícího příkazu:
\begin{listing}
\begin{verbatim}
qsub -pe ompi 5 -q fast.q -l pfq parallel_job.sh
\end{verbatim}
\end{listing}
Parametr za příkazem \textit{ompi} opět říká počet výpočetních jader, parametr \textit{q}~označuje frontu, jejichž seznam je uveden na \cite{sochMPI}. Parametr \textit{parallel\_job.sh} je skript připravený pro spuštění, opět převzatý z~\cite{sochMPI}. Jednotlivé fronty se liší maximální povolenou dobou běhu a~maximálním počtem procesorů.

Dodatečné ladění výkonu je možné na několika místech v~programu. Zaprvé je možné testovat algoritmus s~různými hodnotami určujícími frekvenci kontroly nových zpráv (nyní nastavena na 100). Zadruhé je možné malinko změnit výkon změnou testu určujícího odeslání bílého peška z~procesu root (nyní se odesílá již po $n - 1$ neúspěšných žádostech o~práci). A~za třetí je možné ještě lépe optimalizovat a~zefektivnit dělení zásobníku.

V~průběhu měření a~testování se například ukázalo, že algoritmus potře-buje méně komunikovat, pokud se jako počet stavů, které se maximálně odešlou při dělení zásobníku pevně nastaví na $2$. Uvedená měření jsou ale provedena s variantou, kdy je maximum stavů určeno výrazem $p/2$. Důsledkem toho nejsou naměřené výsledky tak kvalitní, jak by být mohly a~u~většího počtu procesorů je vidět obrovský (a~v~podstatě zbytečný) nárůst komunikační režie.

\section{Naměřené výsledky a vyhodnocení}

Pro měření jsme zvolili tři instance problému uvedené v~tabulce \ref{tab:init}, lišící se počtem uzlů grafu, případně stupněm regularity. Veškeré naměřené časy jsou uváděny v~sekundách.

\begin{table} \begin{center}  \begin{tabular}{|c|c|c|c|}
\hline Jméno & $n$ & $k$ & Sekvenční doba běhu \\ 
\hline 26 & 26 & 14 & 244.182 \\ 
\hline 27-1 & 27 & 12 & 501.045 \\ 
\hline 27-2 & 27 & 10 & 476.535 \\ 
\hline 
\end{tabular} \caption{Měřené instance a sekvenční časy} \label{tab:init} \end{center} \end{table}

\begin{figure}
\includegraphics[width=7.5cm]{figs/speedup-inf.png}
\hglue 0mm
\includegraphics[width=7.5cm]{figs/speedup-eth.png}
\caption{Zrychlení}
\label{fig:speedup}
\end{figure}

\begin{figure}
\includegraphics[width=7.5cm]{figs/efficiency-inf.png}
\hglue 0mm
\includegraphics[width=7.5cm]{figs/efficiency-eth.png}
\caption{Efektivnost}
\label{fig:efficiency}
\end{figure}

\begin{figure}
\includegraphics[width=7.5cm]{figs/time-inf.png}
\hglue 0mm
\includegraphics[width=7.5cm]{figs/time-eth.png}
\caption{Čas}
\label{fig:time}
\end{figure}

\subsection{Naměřené hodnoty}

V~tabulkách \ref{tab:times}~a~\ref{tab:served} jsou uvedeny časy, respektive obsloužené žádosti o~práci pro každý výpočet pro každou komunikační technologii. Na obrázku \ref{fig:speedup}~jsou zobrazeny grafy zrychlení, na obrázku \ref{fig:efficiency} grafy efektivnosti a~na obrázku \ref{fig:time}~jsou do grafu vyneseny hodnoty z~tabulky \ref{tab:times}. Interpretace těchto výsledků je uvedena v~následujícím odstavci.

\begin{table} \begin{center}  \begin{tabular}{|c|c|c|c|c|c|c|}
\hline Počet procesorů & 2 & 4 & 8 & 16 & 24 & 32 \\ 
\hline \multicolumn{7}{|c|}{Infiniband}  \\ 
\hline 26 & 122.652 & 61.1811 & 31.6842 & 20.1632 & 14.4049 & 19.9754 \\ 
\hline 27-1 & 251.251 & 125.637 & 63.7759 & 35.6871 & 26.5521 & 26.73  \\ 
\hline 27-2 & 238.933 & 119.828 & 60.5358 & 33.8641 & 25.2337 & 25.3394 \\ 
\hline \multicolumn{7}{|c|}{Ethernet}  \\ 
\hline 26 & 122.986 & 61.3 & 31.7094 & 21.2084 & 18.8024 & 26.3225 \\
\hline 27-1 & 251.366 & 125.677 & 63.8892 & 38.0021 & 28.5988 & 30.1451 \\
\hline 27-2 & 239.381 & 119.336 & 60.7933 & 34.3402 & 26.059 & 31.2136 \\
\hline 
\end{tabular} \caption{Běhové časy na různém počtu jader a různých sítích} \label{tab:times} \end{center} \end{table}


\begin{table} \begin{center}  \begin{tabular}{|c|c|c|c|c|c|c|}
\hline Počet procesorů & 2 & 4 & 8 & 16 & 24 & 32 \\ 
\hline \multicolumn{7}{|c|}{Infiniband}  \\ 
\hline 26 & 19 & 189 & 6605 & 69333 & 109037 & 367502 \\
\hline 27-1 & 29 & 274 & 6432 & 59614 & 120201 & 332492 \\
\hline 27-2 & 51 & 206 & 6436 & 58591 & 118887 & 325823 \\
\hline \multicolumn{7}{|c|}{Ethernet}  \\ 
\hline 26 & 19 & 217 & 6860 & 75516 & 137474 & 381194 \\
\hline 27-1 & 56 & 207 & 6281 & 59617 & 117005 & 345292 \\
\hline 27-2 & 30 & 241 & 6267 & 59077 & 124003 & 332773 \\
\hline 
\end{tabular} \caption{Celkový počet obsloužených žádostí o práci} \label{tab:served} \end{center} \end{table}

\subsection{Interpretace výsledků}

Při pohledu na grafy zrychlení je vidět, že \textbf{nedosahujeme} lineárního, natož superlineárního zrychlení. Naopak při nasazení příliš velkého počtu jader na příliš malou instanci problému výrazně stoupá nutnost komunikace mezi procesory a~algoritmus naopak zpomaluje.

I~v~tabulce \ref{tab:served} je vidět, jakým tempem narůstá počet žádostí o~práci. Již bylo uvedeno, že při použití pevně dané velikosti dělení zásobníku se algoritmus nejen zrychlí, ale zmenší se i~celková komunikační zátěž. Tuto teorii bohužel nemáme ověřenou na reálném měření na velkém počtu jader, jelikož se nám nepodařilo kvůli velké vytíženosti výpočetního clusteru úlohu včas otestovat. Při nižších počtech jader je však pokles komunikace patrný a~dá se předpokládat, že tento trend bude zhruba konstantní.

Algoritmus pro hledání dárce se zdá být vhodně zvolený, na začátku výpočtu má teoreticky největší stavový prostor k~prohledání proces 1~a~velikost prostoru se se zvyšujícím číslem procesu snižuje, přičemž nejmenší prostor k~prohledání nemá proces $p$, ale proces root~(0), který na začátku distribuuje práci ostatním procesům. Dá se proto předpokládat, že proces root požádá o~práci jako první, a~měl by požádat proces s~největším objemem práce, kterým je proces 1, tedy $p+1$. Jiné varianty jsme netestovali a~nemůžeme tak s~určitostí říci, zda existuje lepší varianta.

Velkých komunikačních úspor lze na druhou stranu dosáhnout vyladěním dělení zásobníku. Již bylo uvedeno, že nastavování různého maximálního počtu stavů pro dělení zásobníku ovlivňuje rychlost i~komunikační složitost výpočtu. Podle zběžných testů se dá dosáhnout zlepšení v~řádu sekund. Ve finální verzi našeho algoritmu tedy nepracujeme s~ideální variantou tohoto algoritmu.

Na grafu \ref{fig:efficiency} je vidět, že efektivnost je zhruba do bodu $n=3p$ velmi dobrá, ovšem pak začíná razantně klesat. Na grafech na obrázku \ref{fig:time} je naopak vidět, že algoritmus v~absolutních číslech zrychluje zhruba do bodu $n = p$, pak jeho čas kvůli velké komunikační režii opět začíná stoupat.

Z~naměřených dat se tedy zdá, že granularita naší implementace je zhruba $n=3p$. Až do momentu $n=p$ sice algoritmus dokáže zrychlovat, efektivnost ale výrazně klesá a~dosažené zrychlení se snižuje.

Zlepšení charakteristik naší implementace může přinést výše uvedená optimalizace dělení zásobníku.

V~průběhu měření se nám podařilo také nalézt a~odstranit několik nepří-jemných chyb, zejména tu, kdy docházelo k~předčasnému ukončení výpočtu. Naopak se objevila chyba, kterou se nám odstranit nepodařilo. Ta se projevuje při spuštění programu na větší počet jader, kdy nedeterministicky dojde k~pádu některého z~procesů, což způsobí ukončení celého programu. Je možné, že tato chyba souvisí s~velkým množstvím komunikace probíhající mezi procesy.

\section{Závěr}
Při práci na úloze jsme se naučili používat nezbytnou podmnožinu knihovny MPI a~v~praxi jsme poznali důležité aspekty vývoje paralelních algoritmů. Vyzkoušeli jsme si, jak některé kroky provedené při návrhu algoritmu ovlivňují celkovou výkonnost a~škálovatelnost. Také jsme se naučili empiricky analyzovat hotový algoritmus a~na základě této analýzy jsme se pokusili navrhnout jeho vylepšení.

Ačkoliv výsledný program není zcela bez chyb, myslíme si, že po drobných úpravách by byl schopný nasazení i~pro mnohem rozsáhlejší instance problému, než které jsme měřili v~naší semestrální práci.

%\section{Literatura}
\renewcommand{\refname}{Literatura}
\bibliographystyle{ieeetr}
{
 \bibliography{refs}
}


\end{document}
